package training;

import java.util.Arrays;

/**
 * @Author liangzai
 * @Description:
 */
public class J25_7_26_Training {
    //删除一个冲突对后最大子数组数目
    public long maxSubarrays(int n, int[][] conflictingPairs) {
        int m = conflictingPairs.length;
        for (int[] pair :conflictingPairs) {
            if (pair[0] > pair[1]) {
                int temp = pair[0];
                pair[0] = pair[1];
                pair[1] = temp;
            }
        }
        Arrays.sort(conflictingPairs,(p1, p2)->(Integer.compare(p1[1],p2[1])));

        int pairPtr = -1;

        int maxA = 0;
        int diff = 0;
        long pairContribute = 0;

        long result = 0;
        long maxContribute = 0;
        for (int end = 1; end <= n; end++) {
            while (pairPtr+1 < m
                    && conflictingPairs[pairPtr+1][1] <= end)
            {
                pairPtr++;
                int thisA = conflictingPairs[pairPtr][0];
                if (thisA >= maxA) {
                    diff = thisA-maxA;
                    maxA = thisA;
                    pairContribute = 0;
                } else {
                    diff = Math.min(diff,maxA-thisA);
                }
            }
            result += end-maxA;
            pairContribute += diff;
            maxContribute = Math.max(maxContribute,pairContribute);
        }

        long ans = result+maxContribute;
        return ans;
    }
}
